1. Field of the Invention
This invention relates to computer systems that employ cache memory systems and, more particularly, to indexing techniques within cache memory systems.
2. Description of the Related Art
A cache memory is a high-speed memory unit interposed in the memory hierarchy of a computer system between a slower system memory and a processor. A cache typically stores recently used data to improve effective memory transfer rates to thereby improve system performance. The cache is usually implemented by semiconductor memory devices having speeds that may be more comparable to the speed of the processor, while the system memory utilizes a less costly, lower speed technology.
A cache memory typically includes a plurality of memory locations that each stores a block or a “line” of two or more words. Each line in the cache has associated with it an address tag that is used to uniquely identify the address of the line. The address tags are typically included within a tag array memory device. Additional bits may further be stored for each line along with the address tag to identify the coherency state of the line.
A processor may read from or write directly into one or more lines in the cache if the lines are present in the cache and if the coherency state allows the access. For example, when a read request originates in the processor for a new word, whether data or instruction, an address tag comparison is made to determine whether a valid copy of the requested word resides in a line of the cache memory. If the line is present, a cache “hit” has occurred and the data is used directly from the cache. If the line is not present, a cache “miss” has occurred and a line containing the requested word is retrieved from the system memory and may be stored in the cache memory. The requested line is simultaneously supplied to the processor to satisfy the request.
Similarly, when the processor generates a write request, an address tag comparison is made to determine whether the line into which data is to be written resides in the cache. If the line is present, the data may be written directly into the cache (assuming the coherency state for the line allows for such modification). If the line does not exist in the cache, a line corresponding to the address being written may be allocated within the cache, and the data may be written into the allocated line.
In many cache systems, in addition to the address tag, an index may be used to determine which location (if direct-mapped) or which set (if set associative) in the cache holds a given cache line of data. In some conventional systems, the index may be some number of bits of the cache line address not included within the tag. However, one drawback to the use of this conventional index is that depending on the type of accesses (e.g., strided accesses), a high level of cache line thrashing may occur.
In other conventional systems another cache indexing function may include hashing the entire cache line address. In such systems, this indexing function may prevent some pathological cases in which strided cache accesses or non-randomly mapped pages have a very high conflict rate. However, this conventional index function may also have drawbacks. For example, this index function may not work well for accesses with strong spatial locality, such as blocks of successive addresses.